mit :: lcs :: tr :: MIT-LCS-TR-212

m

MIT/LCS/TR-212

Digitalized Signatures
and Public Key Functions
as Intractable as Factorization

Michael C. Rabin

This blank page was inserted to preserve pagination.

MIT/LCS/TR-212

DIGITALIZED SIGNATURES AND PUBLIC-KEY FUNCTIONS
AS INTRACTABLE AS FACTORIZATION

Michael 0. Rabin

January 1979

MASSACHUSETTS INSTITUTE OF TECHNOLOGY
LABORATORY FOR COMPUTER SCIENCE

CAMBRIDGE MASSACHUSETTS 02139

This empty page was substituted for a
blank page in the original document.

DIGITALIZED SIGNATURES AND PUBLIC-KEY FUNCTIONS
AS INTRACTABLE AS FACTORIZATION

by
Michael 0. Rabin

Visiting Professor of Applied Mathematics, MIT
Professor of Mathematics, Hebrew University
Jerusalem, Israel

ABSTRACT . We introduce a new class of public-key
functions involving a number n = p-q having two
large prime factors. As usual, the key n is public,
while p and q are the private key used by the
issuer for production of signatures and function
inversion. These functions can be used for all the
applications involving public-key functions proposed
by Diffie and Hellman [2], including digitalized
signatures. We prove that for any given n, if we
can invert the function y = E n (x) for even a small
percentage of the values y then we can factor n .
Thus as long as factorization of large numbers
remains practically intractable, for appropriatly
chosen keys not even a small percentage of signatures
are forgerable. Breaking the RSA function [6] is
at most as hard as factorization , but is not known to
be equivalent to factorization even in the weak sense
that ability to invert all function values entails

-2-

ablllty to factor the key. Computation time for
these functions, I.e. signature verification, is
several hundred times faster than for the RSA scheme
in [6]. Inversion time, using the private key,
is comparable. The almost-everywhere Intractability
of signature-forgery for our functions (on the
assumption that factoring 1s intractable) is of
great practical significance and seems to be the
first proved result of this kind.

Key words. Public-key functions, D1g1tal1zed
signatures, Factorization, Intractable problems.

-3-

INTRODUCTION

In their fundamental paper [2] Diffie and
Hellman have shown how public key trap door functions
can be employed for the solution of various problems
arising in electronic mail, including the production
of digital ized signatures. An example of a public-
key function usable for digitalized signatures was
given in the elegant paper [6 ] by Rivest, Adelman,
and Shamir, who introduced a trap-door one-way function
employing a number n factorable into a product
n = p-q of two large primes. The decoding algorithm
given in [6] for this function requires knowledge
of the factors p, q of n. It is, however, conceivable
that another decoding algorithm exists that does not
involve or imply factorization of n. Thus, breaking
this one-way function is at most as difficult as
factorization, but possibly easier.

We present a different public key function which
can be used for digitalized signatures, and all the
other applications, in the same way as the above-
mentioned function. The function in [6J is 1-1.
Our function is four to one, but this causes only
slight modifications in the applications.

-4-

For this new function we can prove that the
ability to forge signatures or decode messages 1s
equivalent to the ability to factor large numbers.
In fact, for any given n , a signature forgery or
inversion algorithm effective in just a small
percentage of all cases, say one case in a thousand,
already leads to a factorization of n . By
Inversion we mean finding for a number y in the
range of E one of the x such that E(x) ■ y.

In view of the present-day Intractability of
the factorization problem, this fact lends substantial
support to the viability of our public-key function.
As long as it 1s Impossible in practice to factor
large numbers, 1t will be Impossible for a fixed key
to forge signatures even for a small percentage of
all messages.

The fact that we are able to prove, on the
assumption that factoring is hard, that for our
function, for a fixed key n whose factorization
1s not given, Inversion must be hard for almost all
messages 1s of great significance. For other trap
door functions 1t may be the case that even though
worst case complexity or even average complexity
are high, in say one percent of cases Inversion 1s

-5-

easy. From a commercial point of view this would pose
an unacceptable risk. For example, an adversary can
randomly search by computer for messages useful to
him, such as payment instructions, on which he can
forge signatures. To the best of our knowledge, we
have in this article the first example of an almost
everywhere difficult problem of this type.

In addition, computation time for this function
is several hundred times faster, and inversion
when p,q are known, is about eight tlmesrfaster than
the corresponding algorithms in [6]. If we Invert
the RSA function by Chinese Remaindering, as we do
here, then inversion time for the two functions are
comparable.

Theorems 1 and 2 concerning the equivalence of
square-root extraction with factorization, are perhaps
also of independent number-theoretic interest.

1 . THE PUBLIC-KEY FUNCTION

Let n = p-q be the product of two large primes
p,q, and let < b < n.

DEFINITION 1: The function E p b (x) is defined for
< x < n by E .(x) = x(x+b) mod n, < E n b (x)<n.

Computation of E(x), for fixed n,b, requires
one addition, one multiplication, and one division of

-6-

x(x+b) by n to find the residue E b (x). Note

that only the public key n,b, but not the factorization

n = p-q, is required for encoding.

2. INVERSION ALGORITHMS

Given c = x(x+b) modn, we want to find the

four values < x. < n, 1 o < 4 such that Mx^) - c,

We assume of course that the private key, i.e. the
factors of n , are known.

Throughout this paper res(A.B) will denote the
residue of A when divided by B, and (A,B) will
denote the greatest common divisor (g.c.d.) of A
and B.

The decoder, who is the issuer of the public
key n,b, knows the factorization n = p*q. Clearly,
it sufficies to solve the equation x(x+b) =c
separately mod p and mod q and then find a solution
mod n .

Let a be an integer so that a = I mod p ,
a = mod q , and b satisfy b = 1 mod q,
b = mod p . If r and s satisfy the congruence
mod p and mod q respectively, then z = ar + bs
solves the congruence mod n , and x = res (z,nj
is the sought-after solution.

-7-

In what follows let p be a fixed prime. We
shall understand all integers a to be residues
mod p, i.e., 0' <_ a < p . For d a quadratic
residue (q.r.) modp, /a will denote any one of
the two integers such that (/3) = mod p , and
- /d will denote p - /d.

To solve
(1) f(x) = x + bx - c = mod p

2 2

let d ■ b/2 mod p then (x+d) = c + d mod p ,
x = - d t /c+d . We can solve the equation (1)

as soon as we can extract square roots modp, i.e.,

2
solve y - m = mod p .

Assume first that p = 4k - 1 so that 4|(p+l).

Since m is a q.r., m 5 1 mod p. Weclaimthat

(2) i - j/m = m mod p

is one of the two square roots of m. Namely,

l z = m = m«m = m mod p .
Thus one implementation of the function would use p
and q such that p = q = 3 mod 4, and the decoding algorithm

(2).

For p =■ 4k + 1 we directly solve the equation (1)
by a probabilistic algorithm. This is a special case of
Berlekamp's root-finding 1n 6F(p) algorithm given in [1].

-8-

The short proof given here is taken from [5], where
generalizations to GF(p n ) appear. If the roots of (1)
are a, Be GF(p) then x 2 + b x - c = (x - a) (x - 3) The

roots in GF(p) of the polynomial equation x -1=0

are exactly the quadratic residues aeGF(p). Consequently,

if a is a quadratic residue while 3 is not, then

(x - 1, f(x)) = x - a, so that a and subsequently
3 = -(b+a) mod p are readily found.

Assume that a and 3 are of the same type , i.e.,
both quadratic residues (q.r.) or both quadratic non-resi-
dues mod p, and that aj*3- Let < 6 < p then a + 5 and
3+6 are of the same type if and only if (a+6)/(3+6) is
a q.r. mod p. As 6 takes all values £ 6 < p except
6 = -3, the quotient (a+6)/(B+6) takes all values
<_ y < P except y = 1 . Thus for exactly ^— choices
6, a+6 and 3+o will not be of the same type.

Since f(x-6) = (x-ot-6) (x-a-3) » we have that for a
Jiandom choice of < 6 < p, with probability 1/2

(3) (x c -1, f(x-6)) = x-a-6 or x-3-6.

Thus on the average two values of 6 have to be tried for
finding the roots of (1).

The computation of the g.c.d. (3) requires O(logap)
operations in GF(p), i.e., additions and multiplications

-9-

mod p. Namely, by essentially repeated squarlngs start-
ing with x, compute x + h = res(x z , f(x-6)). Whenever
a quadratic polynomial is encountered, divide by f(x-6)
to produce a linear polynomial. Note that x is a formal
variable so that all computations involve just pairs of
residues mod p. Now by (3) , x + h - 1 is x - o - 6 or
x - 3 - 6 , so that -6 - h + 1 is a root of (1).

3. USE IN SIGNATURES

To employ E for signatures the signer P produces
two large primes p,q by use of one of the prime-testing
algorithms [3,7]. He forms n ■ p«q, chooses a number
< b < n and publicizes the pair (n,b) (but not the
factors p.q).

By convention, when wishing to sign a given message,
M,P adds as suffix a word U of an agreed upon length k.
The choice of U 1s randomized each time a message is to
be signed. The signer now compresses Mi * MU by a hash-
ing function to a word C(Mi) = c, so that as a binary
number c < n; see [4]. The computation of C( ) is publicly
known, so that c - C(Mi) is checkable by everybody.

P now checks whether for this c the congruence

(4) x(x+b) = c mod n

-10-

1s solvable.

By the analysis of Section 2, this congruence 1s
solvable if and only if m = c + d 2 is a q.r. mod p and
mod q. Thus testing the solvability of (4) amounts to
computing the Jacobi Symbols (^) and (-J) which is
essentially a g.c.d. type computation.

If congruence (4) is not solvable then P picks another
random Ui and tries Ci ■ C(MUi). The expected number of
tries is 4. When for some U the congruence (4) 1s
solvable for c ■ C(MU), P finds a solution x.

DEFINITION 2 : For a given public key n,b used by P and
an agreed upon compressing function C( ) and Integer k,
P's signature on a message M 1s a pair U,x where
fc(U) = k and x(x + b) = C(MU) mod n.

Anybody can check P's signature by computing
c = C(MU) and testing whether x(x+b) = c mod n.

The randomization of the suffix U of M also adds
protection against possible attacks on the function E.
Without the suffix, an adversary may attempt to feed to
P messages M for his signature, hoping to learn the
factorization of n from the solution of x(x+b) = C(M)
mod n ,which will be produced by P as his signature.
Actually, this does not seem a serious threat because of
the hashing effected by C(M).

-11-

However, the randomized suffix of length k leads
to essentially 2 possible random values for c = C(MU).
Thus for, say, k = 60, the adversary has no effective
control over the congruence (4) that P will solve.

4. INVERSION IS EQUIVALENT TO FACTORIZATION

We now want to show that 1f an adversary can invert
E n . (x) by any algorithm then he can factor n. By invert-
ing we mean finding for y one of the four x such that
E n b^ = y * F"t nd1 ng one such x 1s sufficient for the
would be signature forger, so that we want to show that
this is hard. Thus the problem of, say, forging P's
signilUFtl 1* exactly as intractable as the factorization
of a number n which 1s a product of large primes. As
mentioned in the Introduction, the scheme 1n [6] 1s at
mo4t as safe as factorization but conceivably easier to
crack.

In the following theorem we count an addition of num-
bers a,b, <_ n as one operation.

It is readily seen that 1f we can solve (4) for fixed
n,b and arbitrary c then we can extract square roots,
i.e., solve y 2 = m mod n whenever a solution exists.
Namely, letting b = 2d mod n(n 1s odd) and m » c + d 2
mod n, (4) turns into

-12-

x 2 + 2dx + d 2 = (x+d) 2 = m mod n.
Thus our result follows from

THEOREM 1 : Let AL be an algorithm for finding one of
the solutions of

(5) y 2 = m mod n

whenever a solution exists, and requiring F(n) steps.
There exists an algorithm for factoring n requiring
2F(n) + 21og 2 n steps.

Vn.ooi. Assume that n - p*q 1s a product of two primes,
the case relevant for E n b . The proof easily extends to
the general case.

For any < k < n, (k,n) - 1, there are exactly four
solutions for the congruence

y 2 = k 2 mod n.

Namely, let res(k.p) = r, res(k.q) = s then the solutions
y of this congruence satisfy res(y.p) = *r mod p.res(y.q) ■
= ±s mod q and each of the four sign combinations gives rise
to a different solution. Defining for < yi,y 2 < n,yi*y 2
to mean y? = y| mod n, we see that this equivalence relation
decomposes the set < y < n, (y,n) ■ 1 into classes each
containing four elements.

Denote by /m the solution of (5) by AL for any
m, (m,n) =1. If AL produces more than one solution then

-13-

the factorization algorithm that follows is even further
facil itated .

Choose at random a number < k < n. If (k,n) + 1
then we directly get a factor of n. In practice, this
possibility can be neglected. Compute k 2 = m mod n.

Compute k! = /m by AL . Now, k is i n the equi val ence
class, by the relation a,, of k x . In a random choice of
< k < n, all four possible choices of numbers within
any class are equally likely. Hence with probability 1/2

or

k = ki mod p, k = - ki mod q
k = - ki mod p, k = ki mod q

Therefore with probability 1/2

(6)

(k-ki ,n) = p or q

The computation of /m requires F(n) steps. The
computation of the g.c.d. (6) requires at most log 2 n
subtractions and divisions by 2, of numbers smaller than n,
Hence the expected number of steps is 2F(n) + 2 log 2 n.

If we count bit-operations then subtraction of numbers
smaller than n requires at most log 2 n bit-operations
and the bound is 2F(n) + 2(log 2 n) 2 .

The previous theorem may be strengthened to cover the
situation that for the given key E n b can be decoded in
just a small percentage of all cases.

-14-

THSOREM 2 : If AL solves (5) in F(n) steps for 1/e
of the < m < n, . (m.n) * V, for which (5) has a solution,
then there is an algorithm for factoring n requiring
2eF(n) + 21og 2 n steps.

Vfiooi. As in the proof of Theorem 1, choose a < k < n at
random and compute k 2 = m mod n. Apply AL to find ,/m.
If the computation runs more than F(n) steps abort it
and choose another k. Whenever a root k a - /m is found,
compute (k-ki.n). The analysis in the proof of Theorem 1
implies that with probability 1/2 each such try produces
a factorization of n.

The expected number of choices of k leading to a /m
is § »nd the expected number of 4ucce**(M of AL needed
for a factorization, is 2. Thus the total expected number
of steps is 2eF(n) + 21og 2 n. Note that we embark on the
second phase of the factorization only after a success of
AL in finding /m.

If for example e = 1000, and F(n) were not prohibi-
tively large, then an adversary, could factor n in
2000 F(n) + 21og 2 n steps. Consequently, if no practical
algorithm for factoring n is possible , then no practical
decoding algorithm could work in even 1/1000 of all cases.

-15-

GENERALIZATIONS

The above method of construction of a one-way function
can be extended to employ polynomials or powers of x of
small degrees other than 2.

Assume for example that n = p*q, where p and q
are primes of the form 3k + l . The one-way function will
be E(x) = x 3 mod n. The decoding 1s effected by solving
x 3 - m e mod p and mod q by a probabilistic algorithm
similar to the one used 1n Section 2. Again one can prove
that any algorithm for extracting cubic roots leads, for n
of the above form, to a factorization of n.

The probability that x 3 = w mod n 1s solvable for a
random w 1s 1/9. Thus for utilization ' In signatures the
quadratic scheme seems best.

-16-

REFERENCES

[1] Berlekamp, E.R., Factoring polynomials over large

finite fields, Math, of Coop., vol. 24 (1970), pp. 713-735.

[2] Diffie, W. , and Hellman, M. , New directions in crypto-
graphy, IEEE Trans, of Inf. Theory, IT-22, (November 1976),
pp. 644-654.

[3] Rabin, M. , O., Probabilistic algorithms, Algorithms
and Complexity, Recent Results and New Directions,
J. P. Traub, editor, Academic Press, New York, 1976,
pp t 31*40,

[4] Rabin,' M.O., Digitalized signatures, Foundations of

Secure Computations, R. Lipton and R. DeMillo editors,
Academic Press New York, 1978/

[5] Rabin, M.O., Probabilistic algorithms in finite fields,
submitted for publication.

[6] Rivest, R.L., Shamir A., and Adleman L. , A method for
obtaining digital signatures and public-key crypto-
sy 8 terns, Coram. ACM. vol. 21 (February 1978) .

[7] Solovay, R. , and Strassen, V., A fast monte -carlo test
for primality, SIAM Jour, on Comp. Vol. 6 (1977),
pp. 84-85.